package com.xuan.yupao.utils;


import java.util.List;
import java.util.Objects;

public class AlgorithmUtils {

    /**
     * 最小编辑距离算法
     * @param list1
     * @param list2
     * @return  使两个字符串列表相等所需的最小改变次数
     */
    public static int minDistance(List<String> list1, List<String> list2) {
        int n = list1.size();
        int m = list2.size();
        if (n * m == 0) {
            return n + m;
        }

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) dp[i][0] = i;
        for (int j = 1; j <= m; j++) dp[0][j] = j;


        for (int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(Objects.equals(list1.get(i - 1), list2.get(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) ) + 1;
                }
            }
        }
        return dp[n][m];
    }
}
